#include "deds/alloc.h"
#include <stdio.h>
#include <assert.h>

#ifdef MXMODULE_ALLOC

#   define MX__ALLOC_FENCE_SIZE 16

typedef struct MX__ALLOC_FENCE {
	unsigned char data[MX__ALLOC_FENCE_SIZE];
} MX__ALLOC_FENCE;

typedef struct MX__ALLOC_MEMORY {
	union {
		char a;
		unsigned char b;
		short c;
		unsigned short d;
		int e;
		unsigned int f;
		long g;
		unsigned long h;
		float i;
		double j;
		char dat[2];
		void *k;
		int *l;
	} _align;

	size_t bytes;

	const char *file;
	long line;

	struct MX__ALLOC_MEMORY *next;
	struct MX__ALLOC_MEMORY *prev;

	MX__ALLOC_FENCE fence;
} MX__ALLOC_MEMORY;

/* Memory list */
static unsigned int mx__alloc_started = 0;
static MX__ALLOC_MEMORY *mx__alloc_last = 0;

unsigned int mx__alloc_bytes = 0;
unsigned int mx__alloc_allocs = 0;

const char *mx__alloc_file = 0;
long mx__alloc_line = 0;
long mx__alloc_size = 0;

#   define MX__ALLOC_CAST(ptr)     (((MX__ALLOC_MEMORY*)(ptr)) - 1)

static void mx__alloc_print(void)
{
	MX__ALLOC_MEMORY *ptr = mx__alloc_last;

	if (mx__alloc_last)
		fprintf(stderr, "---Memory---\n");

	while (ptr) {
		fprintf(stderr, "   %i bytes at %p\n", (int) ptr->bytes, (void *) (ptr + 1));
		ptr = ptr->prev;
	}

	if (mx__alloc_last)
		fprintf(stderr, "---Done---\n");
}

static MX__ALLOC_MEMORY *mx__alloc_memory_find(MX__ALLOC_MEMORY * mem)
{
	MX__ALLOC_MEMORY *ptr = mx__alloc_last;

	while (ptr) {
		if (ptr == mem)
			return ptr;

		ptr = ptr->prev;
	}

	/* No match in memory */
	fprintf(stderr, "!!! Gah! Invalid memory %p\n", (void *) (mem + 1));
	abort();

	/* Never get here */
	return 0;
}

static void mx__alloc_memory_add(MX__ALLOC_MEMORY * mem)
{
	mem->prev = mx__alloc_last;
	mem->next = 0;
	if (mx__alloc_last)
		mx__alloc_last->next = mem;
	mx__alloc_last = mem;
}

static void mx__alloc_memory_remove(MX__ALLOC_MEMORY * mem)
{
	mx__alloc_memory_find(mem);

	if (mx__alloc_last == mem)
		mx__alloc_last = mem->prev;

	if (mem->next)
		mem->next->prev = mem->prev;
	if (mem->prev)
		mem->prev->next = mem->next;

	mem->prev = 0;
	mem->next = 0;
}

/* Filling with fences with random data and then checking that the random
   data doesnt change.  We need our own RNG or we would screwup others use
   of rand() becuase of frequent seed changes */
static unsigned long mx__alloc_seed = 93186752l;
static unsigned char mx__alloc_random(void)
{
	mx__alloc_seed = 1588635695l * (mx__alloc_seed % 2) - 1117695901l * (mx__alloc_seed / 2);
	return mx__alloc_seed & 0xff;
}

static void mx__alloc_memory_rand(void *mem, size_t bytes)
{
	unsigned int i = 0;
	unsigned char *ptr = (unsigned char *) mem;

	while (i < bytes)
		ptr[i++] = mx__alloc_random();
}

static void mx__alloc_fence_init(MX__ALLOC_MEMORY * mem)
{
	int i;
	MX__ALLOC_FENCE *myfence = &mem->fence;

	/* Fence at the beginning */
	mx__alloc_seed = (unsigned long) myfence;

	for (i = 0; i < MX__ALLOC_FENCE_SIZE; i++)
		myfence->data[i] = mx__alloc_random();

	/* Fence at the end */
	myfence = (MX__ALLOC_FENCE *) ((unsigned char *) (mem + 1) + mem->bytes);
	mx__alloc_seed = (unsigned long) myfence;
	for (i = 0; i < MX__ALLOC_FENCE_SIZE; i++)
		myfence->data[i] = mx__alloc_random();
}

static void mx__alloc_fence_check(MX__ALLOC_MEMORY * mem)
{
	int i;
	MX__ALLOC_FENCE *myfence = &mem->fence;

	/* Fence at the beginning */
	mx__alloc_seed = (unsigned long) myfence;
	for (i = 0; i < MX__ALLOC_FENCE_SIZE; i++) {
		if (myfence->data[i] != mx__alloc_random()) {
			fprintf(stderr, "!!! Fence (lower) damaged %p\n", (void *) (mem + 1));
			assert(0);
		}
	}

	/* Fence at the end */
	myfence = (MX__ALLOC_FENCE *) ((unsigned char *) (mem + 1) + mem->bytes);
	mx__alloc_seed = (unsigned long) myfence;
	for (i = 0; i < MX__ALLOC_FENCE_SIZE; i++) {
		if (myfence->data[i] != mx__alloc_random()) {
			fprintf(stderr, "!!! Fence (upper) damaged %p\n", (void *) (mem + 1));
			assert(0);
		}
	}
}

void mx___fencecheck(void)
{
	MX__ALLOC_MEMORY *ptr = mx__alloc_last;

	while (ptr) {
		mx__alloc_fence_check(ptr);
		ptr = ptr->prev;
	}
}

void *mx__malloc(size_t bytes)
{
	MX__ALLOC_MEMORY *mem = (MX__ALLOC_MEMORY *) malloc(sizeof(MX__ALLOC_MEMORY) + bytes + sizeof(MX__ALLOC_FENCE));

	assert(mem);
	assert(bytes);

	if (mx__alloc_started == 0) {
		atexit(mx__alloc_print);
		mx__alloc_started = 1;
	}
	mx__alloc_bytes += bytes;
	++mx__alloc_allocs;

	mem->bytes = bytes;
	mem->file = mx__alloc_file;
	mem->line = mx__alloc_line;
	mx__alloc_memory_add(mem);
	mx__alloc_fence_init(mem);
	mx__alloc_memory_rand(mem + 1, bytes);

#   ifdef MX_DETK_ALLOC_LOG
	fprintf(stderr, "malloc  %i at %p\n", (int) bytes, (void *) (mem + 1));
#   endif

	mx___fencecheck();

	return mem + 1;
}

void *mx__realloc(void *themem, size_t bytes)
{
	MX__ALLOC_MEMORY *newmem;
	MX__ALLOC_MEMORY *oldmem = MX__ALLOC_CAST(themem);

	mx__alloc_fence_check(oldmem);
	mx__alloc_memory_remove(oldmem);
	mx__alloc_bytes -= oldmem->bytes;
	--mx__alloc_allocs;

	assert(themem);
	assert(bytes);

	newmem = (MX__ALLOC_MEMORY *) realloc(oldmem, sizeof(MX__ALLOC_MEMORY) + bytes + sizeof(MX__ALLOC_FENCE));
	newmem->bytes = bytes;
	newmem->file = mx__alloc_file;
	newmem->line = mx__alloc_line;

	assert(newmem);

	mx__alloc_memory_add(newmem);
	mx__alloc_fence_init(newmem);
	mx__alloc_bytes += bytes;
	++mx__alloc_allocs;

#   ifdef MX_DETK_ALLOC_LOG
	fprintf(stderr, "realloc %i at %p from %p\n", (int) bytes, (void *) (newmem + 1), (void *) (oldmem + 1));
#   endif

	mx___fencecheck();

	return newmem + 1;
}

void mx__free(void *themem)
{
	MX__ALLOC_MEMORY *mem = MX__ALLOC_CAST(themem);

#   ifdef MX_DETK_ALLOC_LOG
	fprintf(stderr, "free    %i at %p\n", (int) mem->bytes, themem);
#   endif

	mx___fencecheck();

	assert(themem);

	mx__alloc_fence_check(mem);
	mx__alloc_memory_remove(mem);
	mx__alloc_bytes -= mem->bytes;
	--mx__alloc_allocs;

	/* Randomize all memory, even the header and fences */
	mx__alloc_memory_rand(mem, sizeof(MX__ALLOC_MEMORY) + mem->bytes + sizeof(MX__ALLOC_FENCE));

	free(mem);
}

const void *mx__alloc_walk(const void *ptr)
{
	const MX__ALLOC_MEMORY *mem = (const MX__ALLOC_MEMORY *) ptr;

	if (mem)
		mem = mem->prev;
	else
		mem = mx__alloc_last;

	if (mem) {
		mx__alloc_file = mem->file;
		mx__alloc_line = mem->line;
		mx__alloc_size = mem->bytes;
	}
	return mem;
}

void mx___alloc_tag(void *themem, const char *file, const long line)
{
	MX__ALLOC_MEMORY *mem = MX__ALLOC_CAST(themem);
	MX__ALLOC_MEMORY *ptr = mx__alloc_last;

	assert(themem);

	while (ptr) {
		if (ptr == mem) {
			mem->file = file;
			mem->line = line;
			return;
		}
		ptr = ptr->prev;
	}
}

/*
   DEDS
   Data structures and utility functions for C
   Copyright (C) 2006 Douglas Eleveld

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#endif
